package com.example.queue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * 返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
 * <p>
 * 如果没有和至少为 K 的非空子数组，返回 -1 。
 * <p>
 * 示例 1：
 * 输入：A = [1], K = 1
 * 输出：1
 * <p>
 * 示例 2：
 * 输入：A = [1,2], K = 4
 * 输出：-1
 * <p>
 * 示例 3：
 * 输入：A = [2,-1,2], K = 3
 * 输出：3
 */
public class Leetcode862_ShortestSubarray {
    public static void main(String[] args) {
        int[] nums = {2, -1, 2};
        int k = 3;
        // [84,-37,32,40,95]
        // 167
//        nums = new int[] {84, -37, 32, 40, 95};
//        // {0, 84, 47, 79 , 119, 214}
//        k = 167;
        System.out.println(new Solution().shortestSubarray(nums, k));
    }

    static class Solution {
        /**
         * 前缀和 + 滑动窗口 + 双端队列
         * 连续子序列的和 -- 前缀和
         * 区间最短 --- 滑动窗口
         * 数组中存在负数，导致窗口值不单调，导致当我们找到某个窗口和为K，窗内依然可能存在可行解
         * 于是 --维护一个单调队列保证窗口内值的单调性
         *
         * @param nums
         * @param k
         * @return
         */
        public int shortestSubarray2(int[] nums, int k) {
            int res = Integer.MAX_VALUE;
            long[] preSums = new long[nums.length + 1];
            // 求出各个前缀和
            for (int i = 1; i < preSums.length; i++) {
                if (nums[i - 1] >= k) return 1; // 单个元素大于等于K则直接返回
                preSums[i] = preSums[i -1] + nums[i - 1];
            }

            Deque<Integer> queue = new LinkedList<>(); // 队头到队尾保持为单减
            for (int i = 0; i < preSums.length; i++) {
                // 如果当前值<队列尾，那么弹出队尾保持队列单调
                while (!queue.isEmpty() && preSums[i] <= preSums[queue.getLast()])
                    queue.removeLast();

                // 如果队首的值满足当前值-队首值>=K,记录长度并弹出队首
                while (!queue.isEmpty() && preSums[i] - preSums[queue.peekFirst()] >= k)
                    res = Math.min(res, i - queue.pollFirst());

                queue.addLast(i);
            }
            return res == Integer.MAX_VALUE ? -1 : res;
        }

        public int shortestSubarray1(int[] nums, int k) {
            // key为前缀和, value为前缀和的结尾元素索引组成的大根堆
            TreeMap<Long, PriorityQueue<Integer>> preSumMap = new TreeMap<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
            maxHeap.offer(0);
            preSumMap.put(0L, maxHeap);
            int res = Integer.MAX_VALUE;
            long preSum = 0;
            for (int i = 0; i < nums.length; i++) {
                preSum += nums[i];
                PriorityQueue<Integer> newVal = preSumMap.getOrDefault(preSum, new PriorityQueue<>());
                newVal.offer(i + 1);
                preSumMap.put(preSum, newVal);

                Long maxTarget = preSum - k + 1;
                while ((maxTarget = preSumMap.lowerKey(maxTarget)) != null) {
                    int maxIndex = preSumMap.get(maxTarget).peek();
                    res = Math.min(res, i + 1 - maxIndex);
                }
            }

            return res == Integer.MAX_VALUE ? -1 : res;
        }

        public int shortestSubarray(int[] nums, int k) {
            return shortestSubarray2(nums, k);
        }
    }
}
